#include "bigInteger.h"
#include <algorithm>

BigInteger::BigInteger()
{
	length=1;
	isPositive = true;
	data = new char[length+1];
	data[0] = '0';
	data[1] = '\0';
}

BigInteger::BigInteger(char* value)
{
	length = 0;

	if(value[0]=='-')
		isPositive = false;
	else
		isPositive = true;

	while(value[length] != '\0')
		++length;

	if(isPositive){  //положительное
		data = new char[length+1];
		for(int i = 0; i < length; ++i)
			data[i] = value[i];	
	}
	else{  //отрицательное, сдвиг изза минуса
		length--;
		data = new char[length+1];
		for(int i = 0; i < length; ++i)
			data[i] = value[i+1];	
	}
	//нулевой символ в конец для корректности вывода
	data[length]='\0';
}

BigInteger::BigInteger(BigInteger const& value)
{
	length = value.length;
	isPositive = value.isPositive;
	data = new char[length+1];
	for(int i = 0; i < length; ++i){
		data[i] = value.data[i];
	}
	data[length] = '\0';
}

BigInteger::BigInteger(int value)
{
	length = 1;
	isPositive = (value >= 0);		
	int temp = value;
	while(temp/10 != 0)
	{
		temp/=10;
		length++;
	}
	
	data = new char[length+1];
	for(int i = 0; i< length; i++)
	{
		data[length-1-i] = (char)(value%10 + '0');
		value/=10;
	}	
}

BigInteger::~BigInteger()
{
	delete[] data;
}

void BigInteger::swap(BigInteger & b)
{	
	std::swap(data,b.data);		
	std::swap(length,b.length);		
	std::swap(isPositive,b.isPositive);
}

BigInteger& BigInteger::operator = (BigInteger const& b)
{
	if(this != &b)
	{
		BigInteger(b).swap(*this);
		return *this;		
	}
}

BigInteger::operator char*()
{
	return data;
}

bool operator ==(BigInteger const& a, BigInteger const& b)
{
	if(a.length != b.length)
		return false;
	if(a.isPositive != b.isPositive)
		return false;
	for(int i = 0; i < a.length; ++i)
		if(a.data[i] != b.data[i])
			return false;
	return true;
}

bool operator !=(BigInteger const& a, BigInteger const& b)
{
	return !(a==b);
}

bool operator >(BigInteger const& a, BigInteger const& b)
{
	if(a==b)
		return false;
	if(a.isPositive != b.isPositive)
		return a.isPositive;
	int isGreater = a.compareAbs(b);
	 	return a.isPositive ? isGreater : -isGreater; 
}

bool operator <(BigInteger const& a, BigInteger const& b)
{
	return(a != b && !(a > b));
}

bool operator >=(BigInteger const& a, BigInteger const& b)
{
	return (a > b || a == b);
}

bool operator <=(BigInteger const& a, BigInteger const& b)
{
	return (a < b || a == b);
}

BigInteger operator + (BigInteger const& a, BigInteger const& b)
{
	BigInteger res(a);	
	if(a.isPositive == b.isPositive){	
		res = a;
		res.plusAbs(b);
	}
	else{
		if(a.compareAbs(b) > 0){
			res = a;
			res.minusAbs(b); 
		}
		else{
			res = b;
			res.minusAbs(a);	
		}
	}
	return res;	
}

BigInteger operator - (BigInteger const& a, BigInteger const& b)
{
	return a + (-b);
}
BigInteger operator - (BigInteger const& a)
{
	BigInteger res(a);
	res.isPositive = !a.isPositive;
	return res;
}

BigInteger operator * (BigInteger const& a, BigInteger const& b)
{
	BigInteger res(0);
	
	for(int i = 0; i < b.length; ++i){		
		BigInteger currRes(a);	
		currRes.multiplyOneDigit(b.getDigit(i));
		currRes.rollLeft(i);	
		res = res + currRes;
	}
	res.isPositive = (a.isPositive == b.isPositive);
	if(res.length == 1 && res[0] == '0')
		res.isPositive = true;
	return res;	
}

int BigInteger::getSign() const
{
	return (isPositive) ? 1 : -1;
}	

int BigInteger::getDigit(int pos) const
{
	if(pos < length)
		return (data[length-1-pos] - '0');
	else return 0;
}

//больше ли по модулю это число
bool BigInteger::compareAbs(BigInteger const& b) const
{
	if(length == b.length){
		for(int i = length-1; i >=0; --i){
			if(getDigit(i) > b.getDigit(i))
				return true;
			if(getDigit(i) < b.getDigit(i))
				return false;
		}			
		return false; //равны
	}
	else
		return (length > b.length) ? true : false ;
}



//вычитание модулей чисел
//текущее больше чем вычитаемое
void BigInteger::minusAbs(BigInteger const& b)
{
	int al = length;	
	int bl = b.length;	
		
	int newLength = al;
	
	int i = 0;		
	int currDigitA = 0;
	int currDigitB = 0;
	int CF = 0;
	
	char* result = new char[al];
	while(i<al)
	{
		currDigitA = getDigit(i);
		currDigitB = b.getDigit(i);
		
		if(currDigitA - CF >= currDigitB){
			result[al-1-i] = (char)(currDigitA - CF - currDigitB + '0');
			CF = 0;
		}
		else{  //заём из старшего разряда
			result[al-1-i] = (char)(10 + currDigitA - CF - currDigitB + '0');
			CF = 1;
		}	

		if(result[al-1-i] == '0'){
			newLength--;		
		}
		else{
			newLength = al;
		}

		i++;
	} //while
	
	delete[] data;	
	if(newLength == al){ //длина результата = длине уменьшаемого	
		length = al;
		data = result;	
	}
	else{ //длина результата меньше
		if(newLength != 0){
			length = newLength;
			data = new char[length+1];
			for(int i = 0; i< length; ++i){
				data[i] = result[i + (al - newLength)];		
			}
		}
		else{
			length = 1;
			data = new char[length+1];
			data[0] = '0';
		}
		delete[] result;
	}
	data[length]='\0';
}

//сложение модулей чисел
void BigInteger::plusAbs(BigInteger const& b)
{
	int al = length;	
	int bl = b.length;	
	int newLength = (al > bl) ? al : bl;
	
	int i = 0;		
	int currDigitA=0;
	int currDigitB=0;
	int CF = 0;
	
	char* result = new char[newLength+1];	

	while(i<newLength)
	{		
		currDigitA = getDigit(i);
		currDigitB = b.getDigit(i);		
	
		CF = CF + currDigitA + currDigitB;		
	
		if(CF >= 10){ 
			result[newLength-1-i] = (char)(CF - 10 + '0');
			CF = 1;	
		}
		else{
			result[newLength-1-i] = (char)(CF + '0');			
			CF = 0;
		}			
		i++;		
	}
	
	delete[] data;	
	if(CF == 0) //не нужен доп. разряд
	{
		length = newLength;
		data = result;	
	}
	else //нужен доп. разряд
	{
		length = newLength+1;
		data = new char[length+1];
		for(int i = 0; i< length-1; ++i){
			data[i+1] = result[i];		
		}
		data[0] = (char)(CF + '0');
		delete[] result;
	}
	data[length]='\0';
}

//умножить на 10, т.е. сдвинуть влево	
void BigInteger::rollLeft(int n)
{
	if(!(length == 1 && data[0]=='0')){ //если не ноль
		int newLength = length + n;
		char* newData = new char[newLength+1];
		for(int i = 0; i < length; i++)
			newData[i] = data[i];
		for(int i = length; i< newLength; i++)
			newData[i] = '0';
		newData[newLength] = '\0';
		delete [] data;
		data = newData;
		length = newLength;
	}
}

//умножить на 1 цифру
void BigInteger::multiplyOneDigit(int b)
{
	if(b == 0) //умножаем на 0
	{	
		length=1;
		isPositive = true;
		data = new char[length+1];
		data[0] = '0';
		data[1] = '\0';
	}
		int i = 0;		
	int CF = 0;
	char* result = new char[length+1];	
		while(i<length)
	{		
		CF = CF + getDigit(i) * b;		

		if(CF >= 10){ 
			result[length-1-i] = (char)(CF % 10 + '0');
			CF /= 10;	
		}
		else{
			result[length-1-i] = (char)(CF + '0');			
			CF = 0;
		}			
		i++;		
	}

	delete[] data;	
	if(CF == 0) //не нужен доп. разряд
	{
		data = result;	
	}
	else //нужен доп. разряд
	{
		length++;
		data = new char[length+1];
		for(int i = 0; i< length-1; ++i){
			data[i+1] = result[i];		
		}
		data[0] = (char)(CF + '0');
		delete[] result;
	}
	data[length]='\0';
}

